package leetcode.code1921;

import leetcode.IDebug;
import leetcode.helper.H;

// 为什么快排不行？
public class Solution2 implements IDebug {

	public int eliminateMaximum(int[] dist, int[] speed) {
		int len = dist.length;
		int[] arr = new int[len];
		for (int i = 0; i < len; i++) {
			arr[i] = (dist[i] + speed[i] - 1) / speed[i] - 1;
		}
		int ret = this.quick(arr, 0, len - 1) + 1;
		H.print(arr);
		return ret;
	}

	private int quick(int[] arr, int L, int R) {
		if (L >= R) {
			// R抵达右界还在尝试，说明len - 1是答案，否则是未找到
//			return R == arr.length - 1 && arr[R] >= R ? R : -1;
			return -1;
		}
		int index = this.random(L, R);
		index = this.sort(arr, L, R, index);
		if (arr[index] > index) {
			int ret = this.quick(arr, index + 1, R);
			// 右侧找不到，index就是，右侧找到了，ret就是
//			return ret == -1 ? index : ret;
			return ret;
		} else if (arr[index] < index) {
			int ret = this.quick(arr, L, index - 1);
//			return ret == -1 ? index : ret;
			return ret;
		} else {
			int ret = this.quick(arr, index + 1, R);
			return ret == -1 ? index : ret;
		}
	}

	private int sort(int[] nums, int L, int R, int index) {
		this.swap(nums, index, R);
		int num = nums[R];
		int p = L;
		for (int i = L; i < R; i++) {
			if (nums[i] < num) {
				this.swap(nums, p++, i);
			}
		}
		this.swap(nums, p, R);
		return p;
	}

	private void swap(int[] nums, int index, int r) {
		int tmp = nums[index];
		nums[index] = nums[r];
		nums[r] = tmp;
	}

	private int random(int l, int r) {
		return (int) (Math.random() * (r - l + 1)) + l;
	}

	@Override
	public void debug4() {
		H.compare(3, this.eliminateMaximum(H.str2array3("[1,3,4,5,6,7,7,8,9,9,32,10]"),
				H.str2array3("[1,1,2,2,2,1,1,1,1,1,4,3]")));
		H.compare(3, this.eliminateMaximum(H.str2array3("[1,3,4]"), H.str2array3("[1,1,1]")));
		H.compare(1, this.eliminateMaximum(H.str2array3("[1,1,2,3]"), H.str2array3("[1,1,1,1]")));
		H.compare(1, this.eliminateMaximum(H.str2array3("[3,2,4]"), H.str2array3("[5,3,2]")));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution2 so = new Solution2();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
